package q201_rangeBitwiseAnd;

public class Solution_1 {
    /*
    计算两个整数之间所有数字按位与的结果
    方法1：
    首先需要理解该题中得到的结果应该是什么样的
    最直观的方法就是在范围内的每一个数字都执行按位与 最后得到答案 但是会超时
    所以需要观察按位与运算的性质。
    对于一系列的位，例如 [1,1,0,1,1]（纵向看），只要有一个零值的位，那么这一系列位的按位与运算结果都将为零

    所以 我们首先对其所有数字的位 例如9 10 11 12 13
    0 0 0 0 1 0 0 1
    0 0 0 0 1 0 1 0
    0 0 0 0 1 0 1 1
    0 0 0 0 1 1 0 0
    0 0 0 0 1 1 0 1
    可以发现，对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。
    也就是00001000
    这个答案是否正确？
    我们可以简单猜测 假设这些数字直到 i 位之前都是相同的 从 i + 1开始出现有不同的数字
    那么由于 m - n 这一段是连续的数字 那么 i + 1 的这一列一定是这样的一个结构
    0000。。111。。。 也就是一段0和一段1构成
    并且一定存在连续的两个数 x 和 x+1，满足 x 的第 i+1 位为 0，后面全为 1
    这个例子中这两个数就是11 和 12 可以发现 12 的第六列后面都是0 所以第六列以后的所有按位与都是0
    并且从 i + 1开始出现有不同的数字 所以第六列的按位与也是0
    因此：对所有数字执行按位与运算的结果是所有对应二进制字符串的公共前缀再用零补上后面的剩余位。

    问题变成：两个数字的公共前缀
    这里的方法与q191一致 我们知道一种消除数字最后一个1的方法：
    n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果
    所以 如果我们用right边界不停的消除最后一个1 当发现它小于等于left时 也就代表公共前缀后面所有的数字都归零了
     */
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right = right & (right - 1);
        }
        return right;
    }
}
